/*
* leetcode 123. 买卖股票的最佳时机 III
*
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
* */
/*
* */
import java.util.*;
class Solution {
    public int maxProfit(int[] prices) {
        int k=2;
        int[] f=new int[k+2],g=new int[k+2];
        for(int i=0;i<k+2;i++){
            g[i]=-0x3f3f3f;
        }
        for(int p:prices){
            for(int i=k+1;i>0;i--){
                f[i]=Math.max(f[i],g[i-1]+p);
                g[i]=Math.max(g[i],f[i]-p);
            }
        }
        return f[k+1];
    }
}